package com.yvon.service.demo.algorithm.offer;

import com.yvon.service.demo.algorithm.offer.ext.ListNode;

/**
 * 合并两个排序的链表
 * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9825.%20%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%8E%92%E5%BA%8F%E7%9A%84%E9%93%BE%E8%A1%A8/README
 */
public class P25 {
    public static void main(String[] args) {
        Solution solution = new P25().new Solution();
        ListNode<Integer> listNode5 = new ListNode<>(11, null);
        ListNode<Integer> listNode4 = new ListNode<>(8, listNode5);
        ListNode<Integer> listNode3 = new ListNode<>(6, listNode4);
        ListNode<Integer> listNode2 = new ListNode<>(5, listNode3);
        ListNode<Integer> listNode1 = new ListNode<>(3, listNode2);
        ListNode<Integer> head1 = new ListNode<>(2, listNode1);

        ListNode<Integer> listNode15 = new ListNode<>(9, null);
        ListNode<Integer> listNode14 = new ListNode<>(7, listNode15);
        ListNode<Integer> listNode13 = new ListNode<>(4, listNode14);
        ListNode<Integer> listNode12 = new ListNode<>(2, listNode13);
        ListNode<Integer> listNode11 = new ListNode<>(1, listNode12);
        ListNode<Integer> head11 = new ListNode<>(1, listNode11);
        ListNode<Integer> integerListNode = solution.mergeTwoLists(head11, head1);
        ListNode.printLinkedList(integerListNode);
    }

    class Solution {
        ListNode<Integer> mergeTwoLists(ListNode<Integer> l1, ListNode<Integer> l2) {
            ListNode<Integer> dummy = new ListNode<>(0);
            ListNode<Integer> p = dummy;
            while (l1 != null && l2 != null) {
                if (l1.value <= l2.value) {
                    p.next = l1;
                    l1 = l1.next;
                }else {
                    p.next = l2;
                    l2 = l2.next;
                }
                p = p.next;

            }
            p.next = l1 == null ? l2 : l1;
            return dummy.next;
        }
    }
}
